﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//思路，使用链表存放，然后每次找中间的数
//1，先使用list的api
//2，自己建链表
public class MedianFinder2//超时，时间复杂度太大
{
    List<int> list = new List<int>();
    bool isEven = true;
    public MedianFinder2()
    {

    }

    public void AddNum(int num)
    {
        list.Add(num);
        isEven=!isEven;
    }

    public double FindMedian()
    {
       
        list.Sort();
        int mid=list.Count/2;
        if(isEven)//2
        {
            Console.WriteLine("list[mid-1]"+list[mid - 1]);
            Console.WriteLine("list[mid]"+list[mid ]);
            return (list[mid-1]+ list[mid])*0.5;

        }
        else{
            return list[mid];   
        }


    }
}
public class MedianFinder3//使用优先队列，也就是大根堆
{
    PriorityQueue<int, int> queMin;//第一个数是数值，第二个数是他的优先级，数字越小，优先级越高
    PriorityQueue<int, int> queMax;
    public MedianFinder3()
    {
        queMin=new PriorityQueue<int, int>();
         queMax = new PriorityQueue<int, int>();
    }

    public void AddNum(int num)
    {
      

        if(queMin.Count == 0||num <=queMin.Peek()) { //说明小于中位数
            queMin.Enqueue(num, -num);
            //把最大值放到max
            //先判断一下，min的数量应该是比max多一个，多两个才移动
            if(queMin.Count>(queMax.Count+1))
            {
                int min=queMin.Dequeue();

                queMax.Enqueue(min, min);
            }

        }
        else
        {

            queMax.Enqueue(num, num);//越小的数放置在队头，
            if (queMin.Count <queMax.Count )
            {
                int max = queMax.Dequeue();

                queMin.Enqueue(max, -max);
            }

        }


    }

    public double FindMedian()
    {
        if (queMin.Count == queMax.Count)//数量一样，取平均值
        { 
            int min= queMin.Peek();
            int max= queMax.Peek();
            return (min + max) * 0.5;
        }
        else
        {
            return queMin.Peek();
        }


        }
}

public class MyHeap
{
    //heap的数组长度没办法确定啊？？？



}



public class MedianFinder//自己实现大根堆
{
    PriorityQueue<int, int> queMin;//大根堆
    PriorityQueue<int, int> queMax;//小根堆
    public MedianFinder()
    {
        queMin = new PriorityQueue<int, int>();
        queMax = new PriorityQueue<int, int>();
    }

    public void AddNum(int num)
    {


        if (queMin.Count == 0 || num <= queMin.Peek())
        { //说明小于中位数
            queMin.Enqueue(num, -num);
            //把最大值放到max
            //先判断一下，min的数量应该是比max多一个，多两个才移动
            if (queMin.Count > (queMax.Count + 1))
            {
                int min = queMin.Dequeue();

                queMax.Enqueue(min, min);
            }

        }
        else
        {

            queMax.Enqueue(num, num);//越小的数放置在队头，
            if (queMin.Count < queMax.Count)
            {
                int max = queMax.Dequeue();

                queMin.Enqueue(max, -max);
            }

        }


    }

    public double FindMedian()
    {
        if (queMin.Count == queMax.Count)//数量一样，取平均值
        {
            int min = queMin.Peek();
            int max = queMax.Peek();
            return (min + max) * 0.5;
        }
        else
        {
            return queMin.Peek();
        }


    }
}
class Program295
{
    static void Main295(string[] args)
    {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.AddNum(1);    // arr = [1]
        medianFinder.AddNum(2);    // arr = [1, 2]

        Console.WriteLine(medianFinder.FindMedian());
        medianFinder.FindMedian(); // 返回 1.5 ((1 + 2) / 2)
        medianFinder.AddNum(3);    // arr[1, 2, 3]
        Console.WriteLine(medianFinder.FindMedian()); // return 2.0
    }
}
